
class TreeNode:

    def __init__(self, value = False):
        self.value = value
        self.lazy = None
        self.left = None
        self.right = None

class DynamicSegmentTree:

    def __init__(self):
        self.root = TreeNode()

    def push_up(self, cur_node: TreeNode):
        cur_node.value = cur_node.left.value and cur_node.right.value


    # 把开点的操作放到push_down中会更好一些
    def push_down(self, cur_node: TreeNode):
        if cur_node.left is None:
            cur_node.left = TreeNode()
        if cur_node.right is None:
            cur_node.right = TreeNode()
        if cur_node.lazy is not None:
            cur_node.left.value = cur_node.lazy
            cur_node.left.lazy = cur_node.lazy
            cur_node.right.value = cur_node.lazy
            cur_node.right.lazy = cur_node.lazy
            cur_node.lazy = None

    def range_query(self, query_left: int, query_right: int, left: int, right: int, cur_node: TreeNode):
        if query_left <= left and right <= query_right:
            return cur_node.value
        mid = (left + right) // 2
        if cur_node.lazy is not None:
            self.push_down(cur_node)
        res = True
        if query_left <= mid:
            res = res and self.range_query(query_left, query_right, left, mid, cur_node.left)
        if mid < query_right:
            res = res and self.range_query(query_left, query_right, mid + 1, right, cur_node.right)
        return res

    def range_update(self, value: bool, query_left: int, query_right: int, left: int, right: int, cur_node: TreeNode):
        if query_left <= left and right <= query_right:
            cur_node.value = value
            if left != right:
                cur_node.lazy = value
            return
        mid = (left + right) // 2
        self.push_down(cur_node)
        if query_left <= mid:
            self.range_update(value, query_left, query_right, left, mid, cur_node.left)
        if mid < query_right:
            self.range_update(value, query_left, query_right, mid + 1, right, cur_node.right)
        self.push_up(cur_node)


MAX = 10**9
# https://leetcode.cn/problems/range-module/
class RangeModule:
    def __init__(self):
        self.segment_tree = DynamicSegmentTree()

    def addRange(self, left: int, right: int) -> None:
        self.segment_tree.range_update(True, left, right - 1, 0, MAX, self.segment_tree.root)


    def queryRange(self, left: int, right: int) -> bool:
        return self.segment_tree.range_query(left, right - 1, 0, MAX, self.segment_tree.root)


    def removeRange(self, left: int, right: int) -> None:
        self.segment_tree.range_update(False, left, right - 1, 0, MAX, self.segment_tree.root)

